#include <iostream>
using std::endl;
using std::cout;
using std::cin;

struct matrixTerm
{ // 三元组结构体定义
	int row, col, value;
	matrixTerm &operator=(matrixTerm &x)
	{ // 运算符重载 ，赋值*this = x
		row = x.row;
		col = x.col;
		value = x.value;
		return *this;
	}
};
const int maxsize = 199999; // 新matrixTerm创建最大容量设定

class sparseMatrix // 稀疏矩阵类定义
{
private:
	int Rows;            // 行
	int Cols;            // 列
	int Terms;           // 非零元素个数
	matrixTerm *element; // 用来存非零元素的数组
	int maxSize;         // 数组最大容量
public:
	sparseMatrix(int n, int m) // 构造函数
	{
		element = new matrixTerm[maxsize];
		Rows = n;
		Cols = m;
		Terms = 0;
	}
	~sparseMatrix() { delete[] element; } // 析构函数
	sparseMatrix &operator=(sparseMatrix &a)
	{ // 运算符重载 ，赋值*this = a
		Rows = a.Rows;
		Cols = a.Cols;
		Terms = a.Terms;
		maxSize = a.maxSize;
		for (int i = 0; i < Terms; i++)
			element[i] = a.element[i];
		return *this;
	}
	void inputAelement(int x, int y, int v); // 辅助函数——非0值输入
	void initial();              // 重置1
	int multiply(sparseMatrix &a);           // 乘法2
	int add(sparseMatrix &a);                // 加法3
	void output();                           // 输出4
	void transpose();                        // 转置5
};

// 辅助函数——非0值输入，更新三元组
void sparseMatrix::inputAelement(int x, int y, int v)
{
	matrixTerm New;
	New.row = x;   // 行序号
	New.col = y;   // 列序号
	New.value = v; // 非零元素值
	element[Terms] = New;
	Terms++;
}

// 重置1
void sparseMatrix::initial()
{
	int n = 0;
	int m = 0;
	cin >> n >> m;
	Rows = n;
	Cols = m;
	Terms = 0;
	for (int i = 1; i <= Rows; ++i)
	{ // 按行优先顺序输入矩阵的各个元素
		for (int j = 1; j <= Cols; ++j)
		{
			int b;
			cin >> b;
			if (b != 0)
			{
				element[Terms].row = i;
				element[Terms].col = j;
				element[Terms].value = b;
				Terms++;
			}
		}
	}
}

// 乘法2
int sparseMatrix::multiply(sparseMatrix &Q)
{
	// 有效性检验
	if (Cols != Q.Rows)
	{ // 按矩阵乘法C[m,n]= P[m,k] ×Q[k,n]，需要有Cols=Q.Rows
		*this = Q;
		return -1;
	}
	else
	{
		// 取乘数P的行和乘数Q的列构建结果sparseMatrix
		sparseMatrix C(Rows, Q.Cols);
		int num[10000];    // 每行非零元素的个数
		int Index[10000];  // 每行第一个非零元素对应的索引
		int Answer[10000]; // 存放乘法结果
		
		// 每行计数清零
		for (int i = 1; i <= Q.Rows; i++)
			num[i] = 0;
		// 计数得第i行对应非零元素个数
		for (int i = 0; i < Q.Terms; i++)
		{
			if (Q.element[i].value != 0)
				num[Q.element[i].row]++;
		}
		// 第i行第一个非零元素索引
		Index[1] = 0;
		for (int i = 2; i <= Q.Terms; i++)
			Index[i] = Index[i - 1] + num[i - 1];
		
		// 开始乘法计算C[m,n]= P[m,k] ×Q[k,n]
		int p = 0;
		for (int i = 1; i <= Rows && p < Terms; i++)
		{
			// 赋初值0
			for (int j = 1; j <= Q.Cols; j++)
				Answer[j] = 0;
			while (p < Terms && element[p].row == i) // 循环条件为仍有非零元素且第i行有非零元素
			{
				int t = element[p].col;
				if (num[t] != 0) // P有非0元素的行对应的Q里的列任有非0元素
				{                // 如果都是0了，乘法所得也不会是非0，这个判断起简化作用
					for (int q = Index[t]; q < Index[t] + num[t]; q++)
						// 计算对应i行每列的乘积
						Answer[Q.element[q].col] += element[p].value * Q.element[q].value;
				}
				// 继续下一个非零元素
				p++;
			}
			for (int k = 1; k <= Q.Cols; k++)
			{ // 结果中的非0元素导出三元组
				if (Answer[k] != 0)
				{
					C.element[C.Terms].value = Answer[k];
					C.element[C.Terms].row = i;
					C.element[C.Terms].col = k;
					C.Terms++;
				}
			}
		}
		*this = C;
		return 0;
	}
}

// 加法3
int sparseMatrix::add(sparseMatrix &Q)
{
	if (Q.Cols != Cols || Q.Rows != Rows) // 根据矩阵加法规则，行列不等不符合
	{
		*this = Q;
		return -1;
	}
	else
	{
		sparseMatrix C(Rows, Cols); // 设置结果矩阵的特征
		int it = 0, ib = 0;
		while (it != Terms && ib != Q.Terms) // 遍历，把相关的项相加
		{                                    // 行主索引加上每一项的列数
			int tIndex = (element[it]).row * Cols + (element[it]).col;
			int bIndex = (Q.element[ib]).row * Cols + (Q.element[ib]).col;
			if (tIndex < bIndex)
			{ // Q项在后
				C.element[C.Terms].col = element[it].col;
				C.element[C.Terms].row = element[it].row;
				C.element[C.Terms].value = element[it].value;
				it++;
				C.Terms++;
			}
			else if (tIndex == bIndex)
			{ // 两项在同一个位置
				if ((element[it]).value + (Q.element[ib]).value != 0)
				{ // 仅当相加后不为0时加入c
					C.element[C.Terms].col = (element[it]).col;
					C.element[C.Terms].row = (element[it]).row;
					C.element[C.Terms].value = (element[it]).value + (Q.element[ib]).value;
					C.Terms++;
				}
				it++;
				ib++;
			}
			else
			{
				C.element[C.Terms].col = Q.element[ib].col;
				C.element[C.Terms].row = Q.element[ib].row;
				C.element[C.Terms].value = Q.element[ib].value;
				ib++;
				C.Terms++;
			}
		}
		// 复制剩余项
		for (; it != Terms; it++)
		{
			C.element[C.Terms].col = element[it].col;
			C.element[C.Terms].row = element[it].row;
			C.element[C.Terms].value = element[it].value;
			C.Terms++;
		}
		for (; ib != Q.Terms; ib++)
		{
			C.element[C.Terms].col = Q.element[ib].col;
			C.element[C.Terms].row = Q.element[ib].row;
			C.element[C.Terms].value = Q.element[ib].value;
			C.Terms++;
		}
		*this = C;
		return 0;
	}
}

// 输出4
void sparseMatrix::output()
{
	int i, j, k = 0;
	cout << Rows << " " << Cols << endl;
	for (i = 0; i < Rows; i++) // 遍历输出
	{
		for (j = 0; j < Cols; j++)
		{
			if (k < Terms && element[k].row == i + 1 && element[k].col == j + 1)
			{
				cout << element[k].value << " ";
				k++;
			}
			else
				cout << 0 << " ";
		}
		cout << endl;
	}
}

// 转置5
void sparseMatrix::transpose()
{
	// 设置转置矩阵特征
	sparseMatrix b(Cols, Rows);
	b.Terms = Terms;
	b.Cols = Rows;
	b.Rows = Cols;
	// 初始化
	int *colSize = new int[Cols + 1]; // 矩阵第i列的非零元素个数
	int *rowNext = new int[Cols + 1]; // 矩阵第i列第一个非零元素索引
	
	// 计算待转置矩阵中每一列非0元素的个数
	for (int i = 1; i <= Cols; i++)
		colSize[i] = 0;
	for (int i = 0; i < Terms; i++)
		colSize[element[i].col]++;
	// 确定矩阵第i列第1个非0元素的对应索引
	rowNext[1] = 0;
	for (int i = 2; i <= Cols; i++)
		rowNext[i] = rowNext[i - 1] + colSize[i - 1];
	// 上述几步和乘法中同理，提高程序针对稀疏矩阵运算效率
	
	// 实施从*this到b的转置复制
	for (int i = 0; i < Terms; i++)
	{
		int j = rowNext[element[i].col];
		// 行列转置
		b.element[j].row = element[i].col;
		b.element[j].col = element[i].row;
		b.element[j].value = element[i].value;
		rowNext[element[i].col] = rowNext[element[i].col] + 1;
		// 对应列rowNext索引+1，以防同一列有多个非零元素 (防撞）
	}
	*this = b;
}

int main()
{
	sparseMatrix P(0, 0);
	int w;           // 操作个数
	int panduan = 0; // 各种不合法输出工具变量
	int n;           // 矩阵行数
	int m;           // 矩阵列数
	int t;           // 矩阵非0元素个数
	int trans;       // 操作编码
	cin >> w;
	for (int i = 0; i < w; i++)
	{
		cin >> trans;
		switch (trans)
		{
			// 重置矩阵
		case 1:
			{
				P.initial();
			}
			
			// 矩阵乘法
		case 2:
			{
				cin >> n >> m;
				cin >> t;
				sparseMatrix Q1(n, m);
				for (int i = 0; i < t; i++)
				{
					// Q矩阵非零元素的行、列序号及非0元素值
					int x, y, v;
					cin >> x >> y >> v;
					Q1.inputAelement(x, y, v);
				}
				panduan = P.multiply(Q1);
				if (panduan == -1)
					cout << panduan << endl;
			}
			
			// 矩阵加法
		case 3:
			{
				cin >> n >> m;
				cin >> t;
				sparseMatrix Q2(n, m);
				for (int i = 0; i < t; i++)
				{
					int x, y, v;
					cin >> x >> y >> v;
					Q2.inputAelement(x, y, v);
				}
				panduan = P.add(Q2);
				if (panduan == -1)
					cout << panduan << endl;
			}
			
			// 输出操作
		case 4:
			{
				P.output();
			}
			
			// 转置
		case 5:
			{    
				P.transpose();
			}
			
			
		}
	} 
	return 0;
}
